{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Guess the Word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #string #game-theory #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #字符串 #博弈 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSecretWord"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #猜猜这个单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <strong>不同</strong> 字符串组成的单词列表&nbsp;<code>words</code> ，其中 <code>words[i]</code>&nbsp;长度均为&nbsp;<code>6</code> 。<code>words</code> 中的一个单词将被选作秘密单词 <code>secret</code>&nbsp;。</p>\n",
    "\n",
    "<p>另给你一个辅助对象&nbsp;<code>Master</code> ，你可以调用&nbsp;<code>Master.guess(word)</code> 来猜单词，其中参数 <code>word</code> 长度为 6 且必须是 <code>words</code> 中的字符串。</p>\n",
    "\n",
    "<p><code>Master.guess(word)</code> 将会返回如下结果：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>word</code> 不是 <code>words</code> 中的字符串，返回 <code>-1</code> ，或者</li>\n",
    "\t<li>一个整数，表示你所猜测的单词 <code>word</code> 与 <strong>秘密单词</strong>&nbsp;<code>secret</code>&nbsp;的准确匹配（值和位置同时匹配）的数目。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每组测试用例都会包含一个参数 <code>allowedGuesses</code> ，其中 <code>allowedGuesses</code> 是你可以调用 <code>Master.guess(word)</code> 的最大次数。</p>\n",
    "\n",
    "<p>对于每组测试用例，在不超过允许猜测的次数的前提下，你应该调用 <code>Master.guess</code> 来猜出秘密单词。最终，你将会得到以下结果：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果你调用 <code>Master.guess</code> 的次数大于 <code>allowedGuesses</code> 所限定的次数或者你没有用 <code>Master.guess</code> 猜到秘密单词，则得到 <strong><code>\"Either you took too many guesses, or you did not find the secret word.\"</code> 。</strong></li>\n",
    "\t<li>如果你调用 <code>Master.guess</code> 猜到秘密单词，且调用 <code>Master.guess</code> 的次数小于或等于 <code>allowedGuesses</code> ，则得到 <strong><code>\"You guessed the secret word correctly.\"</code> 。</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>生成的测试用例保证你可以利用某种合理的策略（而不是暴力）猜到秘密单词。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>secret = \"acckzz\", words = [\"acckzz\",\"ccbazz\",\"eiowzz\",\"abcczz\"], allowedGuesses = 10\n",
    "<strong>输出：</strong>You guessed the secret word correctly.\n",
    "<strong>解释：</strong>\n",
    "master.guess(\"aaaaaa\") 返回 -1 ，因为 \"aaaaaa\" 不在 words 中。\n",
    "master.guess(\"acckzz\") 返回 6 ，因为 \"acckzz\" 是秘密单词 secret ，共有 6 个字母匹配。\n",
    "master.guess(\"ccbazz\") 返回 3 ，因为 \"ccbazz\" 共有 3 个字母匹配。\n",
    "master.guess(\"eiowzz\") 返回 2 ，因为 \"eiowzz\" 共有 2 个字母匹配。\n",
    "master.guess(\"abcczz\") 返回 4 ，因为 \"abcczz\" 共有 4 个字母匹配。\n",
    "一共调用 5 次 master.guess ，其中一个为秘密单词，所以通过测试用例。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>secret = \"hamada\", words = [\"hamada\",\"khaled\"], allowedGuesses = 10\n",
    "<strong>输出：</strong>You guessed the secret word correctly.\n",
    "<strong>解释：</strong>共有 2 个单词，且其中一个为秘密单词，可以通过测试用例。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 100</code></li>\n",
    "\t<li><code>words[i].length == 6</code></li>\n",
    "\t<li><code>words[i]</code> 仅由小写英文字母组成</li>\n",
    "\t<li><code>words</code> 中所有字符串 <strong>互不相同</strong></li>\n",
    "\t<li><code>secret</code> 存在于 <code>words</code> 中</li>\n",
    "\t<li><code>10 &lt;= allowedGuesses &lt;= 30</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [guess-the-word](https://leetcode.cn/problems/guess-the-word/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [guess-the-word](https://leetcode.cn/problems/guess-the-word/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"acckzz\"\\n[\"acckzz\",\"ccbazz\",\"eiowzz\",\"abcczz\"]\\n10', '\"hamada\"\\n[\"hamada\",\"khaled\"]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        def helper(word, tar):\n",
    "            res = 0\n",
    "            for i in range(6):\n",
    "                if word[i] == tar[i]:\n",
    "                    res += 1\n",
    "            return res\n",
    "\n",
    "        for i in range(30):\n",
    "            tar = random.choice(words)\n",
    "            cnt = master.guess(tar)\n",
    "            if cnt == 6:\n",
    "                break\n",
    "            candidate = []\n",
    "            for word in words:\n",
    "                if helper(word, tar) == cnt:\n",
    "                    candidate.append(word)\n",
    "            words = candidate\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        def func(w1, w2):\n",
    "            return sum(l1 == l2 for l1, l2 in zip(w1, w2))\n",
    "        while True:\n",
    "            shuffle(words)\n",
    "            g = master.guess(words[0])\n",
    "            if   g == 6: return\n",
    "            elif g == 0: words = [w for w in words[1:] if func(w, words[0]) == 0]\n",
    "            else       : words = [w for w in words[1:] if func(w, words[0]) >= g]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        n = len(words)\n",
    "        degs = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(6):\n",
    "                    if words[i][k] == words[j][k]:\n",
    "                        degs[i][j] += 1\n",
    "        tmp1 = list(range(n))\n",
    "        for _ in range(30):\n",
    "            k = random.choice(tmp1)\n",
    "            d = master.guess(words[k])\n",
    "            if len(tmp1) == 1:\n",
    "                break\n",
    "            tmp2 = []\n",
    "            for i in tmp1:\n",
    "                if degs[k][i] == d:\n",
    "                    tmp2.append(i)\n",
    "            tmp1 = tmp2\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        def diff(a,b):\n",
    "            res=0\n",
    "            for i in range(len(a)):\n",
    "                if a[i]==b[i]:\n",
    "                    res+=1\n",
    "            return res\n",
    "        \n",
    "        def var(l):\n",
    "            res=0\n",
    "            m=sum(l)/len(l)\n",
    "            return sum([(x-m)**2 for x in l])/len(l)\n",
    "\n",
    "        def minlen(words):\n",
    "            ti, tv = 0, inf\n",
    "            for i in range(len(words)):\n",
    "                s = [0]*7\n",
    "                for j in range(len(words)):\n",
    "                    s[diff(words[i], words[j])]+=1\n",
    "                v=var(s)\n",
    "                # print(words[i], s, v)\n",
    "                if v<tv:\n",
    "                    tv, ti = v, i\n",
    "            return ti\n",
    "\n",
    "        res=words\n",
    "        while len(res)>1:\n",
    "            i=minlen(res)\n",
    "            # print(i, res[i])\n",
    "            t=master.guess(res[i])\n",
    "            if t==6: break\n",
    "            s=[]\n",
    "            for _ in res:\n",
    "                if diff(res[i], _)==t:\n",
    "                    s.append(_)\n",
    "            # print(res[i], t, s)\n",
    "            res=s\n",
    "        master.guess(res[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        while 1:\n",
    "            w0 = words.pop()\n",
    "            if not (score := master.guess(w0)):\n",
    "                words = [w for w in words[::-1] if not any(starmap(eq, zip(w, w0)))]\n",
    "            elif score == 6: return\n",
    "            else:\n",
    "                words = [w for w in words if sum(starmap(eq, zip(w, w0))) == score]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "from random import choice\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        now = 0\n",
    "        strict = []\n",
    "        while True:\n",
    "            flag = True\n",
    "            word = choice(words)\n",
    "            words.remove(word)\n",
    "            for s, num in strict:\n",
    "                count = 0\n",
    "                for i in range(6):\n",
    "                    if s[i] == word[i]:\n",
    "                        count += 1\n",
    "                if count != num:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                num = master.guess(word)\n",
    "                if num == 6:\n",
    "                    break\n",
    "                strict.append((word, num))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "'''\n",
    "方法 1：启发式极小化极大算法\n",
    "\n",
    "显然，可行单词列表中的单词越少越好。如果数据随机，那么我们可以认定这个情况是普遍的。\n",
    "现在，利用极小化极大算法猜测可行的单词列表。如果我们开始有 N 个单词，我们通过迭代去选择可行单词。\n",
    "\n",
    "算法\n",
    "存储 H[i][j] 为 wordlist[i] 和 wordlist[j] 单词匹配数。每次猜测要求之前没有猜过，\n",
    "按照上面的说法实现极小化极大算法，每次选择猜测的单词是当前可行单词中的一个。\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:\n",
    "        N = len(wordlist)\n",
    "        self.H = [[sum(a==b for a,b in zip(wordlist[i], wordlist[j]))\n",
    "                   for j in range(N)] for i in range(N)]\n",
    "\n",
    "        possible, path = range(N), ()\n",
    "        while possible:\n",
    "            guess = self.solve(possible, path)\n",
    "            matches = master.guess(wordlist[guess])\n",
    "            if matches == len(wordlist[0]): return\n",
    "            possible = [j for j in possible if self.H[guess][j] == matches]\n",
    "            path = path + (guess,)\n",
    "\n",
    "    def solve(self, possible, path = ()):\n",
    "        if len(possible) <= 2: return possible[0]\n",
    "\n",
    "        ansgrp, ansguess = possible, None\n",
    "        for guess, row in enumerate(self.H):\n",
    "            if guess not in path:\n",
    "                groups = [[] for _ in range(7)]\n",
    "                for j in possible:\n",
    "                    if j != guess:\n",
    "                        groups[row[j]].append(j)\n",
    "                maxgroup = max(groups, key = len)\n",
    "                if len(maxgroup) < len(ansgrp):\n",
    "                    ansgrp, ansguess = maxgroup, guess\n",
    "\n",
    "        return ansguess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:\n",
    "        \n",
    "        def get_char_frequency():\n",
    "            \"\"\"Calculate the frequency of each character at each position in the wordlist.\"\"\"\n",
    "            char_freq = [[0] * 26 for _ in range(6)]\n",
    "            for word in wordlist:\n",
    "                for i, char in enumerate(word):\n",
    "                    char_freq[i][ord(char) - ord('a')] += 1\n",
    "            return char_freq\n",
    "\n",
    "        def score_word(word, char_freq):\n",
    "            \"\"\"Calculate the score of a word based on the character frequency.\"\"\"\n",
    "            return sum(char_freq[i][ord(char) - ord('a')] for i, char in enumerate(word))\n",
    "        \n",
    "        def best_guess_word(char_freq):\n",
    "            \"\"\"Return the word with the highest score.\"\"\"\n",
    "            return max(wordlist, key=lambda word: score_word(word, char_freq))\n",
    "        \n",
    "        def word_match_count(a, b):\n",
    "            \"\"\"Count how many positions the two words have the same character.\"\"\"\n",
    "            return sum(ac == bc for ac, bc in zip(a, b))\n",
    "        \n",
    "        def filter_candidates(guessed_word, match_count):\n",
    "            \"\"\"Filter the wordlist to contain only words that have the same match count with the guessed word.\"\"\"\n",
    "            return [word for word in wordlist if word_match_count(word, guessed_word) == match_count]\n",
    "\n",
    "        # Initialize character frequency table\n",
    "        char_freq = get_char_frequency()\n",
    "\n",
    "        while wordlist:\n",
    "            # Guess the best word and get the match count from wordlist\n",
    "            guessed_word = best_guess_word(char_freq)\n",
    "            match_count = master.guess(guessed_word)\n",
    "\n",
    "            # If the guessed word is correct, return\n",
    "            if match_count == 6:\n",
    "                return\n",
    "\n",
    "            # Update wordlist based on the match count\n",
    "            wordlist = filter_candidates(guessed_word, match_count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        n = len(words)\n",
    "        dist = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(6):\n",
    "                    if words[i][k] == words[j][k]:\n",
    "                        dist[i][j] += 1\n",
    "        tmp1 = list(range(n))\n",
    "        for _ in range(30):\n",
    "            degs = [0] * len(tmp1)\n",
    "            guess = 0\n",
    "            for i in range(len(tmp1)):\n",
    "                for j in tmp1:\n",
    "                    degs[i] += dist[tmp1[i]][j]\n",
    "                if degs[i] > degs[guess]:\n",
    "                    guess = i\n",
    "            d = master.guess(words[tmp1[guess]])\n",
    "            if d == 6: break\n",
    "            tmp2 = []\n",
    "            for i in tmp1:\n",
    "                if dist[tmp1[guess]][i] == d:\n",
    "                    tmp2.append(i)\n",
    "            tmp1 = tmp2\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is Master's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "# class Master:\r\n",
    "#     def guess(self, word: str) -> int:\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\r\n",
    "        def distince(w1, w2):\r\n",
    "            return sum([s1 == s2 for s1, s2 in zip(w1, w2)])\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        while True:\r\n",
    "            w = words[0]\r\n",
    "            d = master.guess(w)\r\n",
    "            if d == 6:\r\n",
    "                return w\r\n",
    "            else:\r\n",
    "                choose = [s for s in words if distince(s, w) == d]\r\n",
    "                words = list(set(words)&set(choose))\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        def get(words):\n",
    "            n = len(words)\n",
    "            cnts = [[0 for _ in range(n)] for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    cnt = 0\n",
    "                    for k in range(6):\n",
    "                        if words[i][k] == words[j][k]: cnt += 1\n",
    "                    cnts[i][j] = cnt\n",
    "                    cnts[j][i] = cnt\n",
    "            mi = idx = -1\n",
    "            for i in range(n):\n",
    "                tmp = collections.Counter([cnts[i][j] for j in range(n) if i != j])\n",
    "                mx = max([tmp[k] for k in tmp])\n",
    "                if mi == -1 or mi > mx:\n",
    "                    mi, idx = mx, i\n",
    "            return idx, cnts[idx]\n",
    "        while len(words) >= 1:\n",
    "            if len(words) == 1:\n",
    "                master.guess(words[0])\n",
    "                return\n",
    "            idx, vals = get(words)\n",
    "            val, nexts = master.guess(words[idx]), []\n",
    "            if val == 'You guessed the secret word correctly.': return\n",
    "            for i, word in enumerate(words):\n",
    "                if i != idx and vals[i] == val: nexts.append(word)\n",
    "            words = nexts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        def func(w1, w2):\n",
    "            return sum(l1 == l2 for l1, l2 in zip(w1, w2))\n",
    "        while True:\n",
    "            shuffle(words)\n",
    "            g = master.guess(words[0])\n",
    "            if   g == 6: return\n",
    "            elif g == 0: words = [w for w in words[1:] if func(w, words[0]) == 0]\n",
    "            else       : words = [w for w in words[1:] if func(w, words[0]) >= g]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        # greedily try guessing with max score, where score is defined based on occurance of char at each pos\n",
    "        pos_al_count = [[0] * 26 for _ in range(6)]\n",
    "        for word in words:\n",
    "            for i in range(6):\n",
    "                pos_al_count[i][ord(word[i]) - ord('a')] += 1\n",
    "\n",
    "        def score(pos_al_count, word) -> int:\n",
    "            return sum(pos_al_count[i][ord(word[i]) - ord('a')] for i in range(6))\n",
    "\n",
    "        def filter_words(candidate, words_list, match) -> List[str]:\n",
    "            res = []\n",
    "            for word in words_list:\n",
    "                if sum(char1 == char2 for char1, char2 in zip(candidate, word)) == match:\n",
    "                    res.append(word)\n",
    "\n",
    "            return res\n",
    "\n",
    "        while words:\n",
    "        # get word with max score\n",
    "           candidate = max(words, key = lambda word: score(pos_al_count, word))\n",
    "\n",
    "           match = master.guess(candidate)\n",
    "\n",
    "           if match == 6:\n",
    "               return candidate\n",
    "            \n",
    "           words = filter_words(candidate, words, match)\n",
    "\n",
    "        return\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "\n",
    "        def check(w1, w2, cnt):\n",
    "            return sum(w1[i] == w2[i] for i in range(6)) == cnt\n",
    "\n",
    "        def find(possible):\n",
    "            n = len(possible)\n",
    "            H = [[0] * n for _ in range(n)]\n",
    "            maxarg, maxval = -1, inf\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    H[i][j] = sum(possible[i][k] == possible[j][k] for k in range(6))\n",
    "                counter = Counter(H[i])\n",
    "                mx = max(counter.values())\n",
    "                if mx < maxval:\n",
    "                    maxarg = i\n",
    "                    maxval =  mx\n",
    "            print(maxval)\n",
    "            return possible[maxarg]\n",
    "\n",
    "        while True:\n",
    "            x = find(words)\n",
    "            res = master.guess(x)\n",
    "            if res == 6:\n",
    "                return\n",
    "            words = [word for word in words if check(x, word, res)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        while 1:\n",
    "            if (score := master.guess(w0 := words.pop())) == 6: return\n",
    "            words = [w for w in words[::-1] if sum(starmap(eq, zip(w, w0))) == score]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        while 1:\n",
    "            w0 = words.pop()\n",
    "            if not (score := master.guess(w0)):\n",
    "                words = [w for w in words[::-1] if not any(starmap(eq, zip(w, w0)))]\n",
    "            elif score == 6: return\n",
    "            else:\n",
    "                words = [w for w in words if sum(starmap(eq, zip(w, w0))) == score]\n",
    "            print(w0, score, len(words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        pos_cnt = [[0] * 26 for _ in range(6)] # fixed size\n",
    "        for i in range(len(words)):\n",
    "            for j in range(6):  # 26 alphabat for each char\n",
    "                pos_cnt[j][ord(words[i][j]) - ord('a')] += 1\n",
    "\n",
    "        def score(word) -> int:\n",
    "            # calculate score based on summation of occurance for each char pos in word\n",
    "            return sum(pos_cnt[i][ord(word[i]) - ord('a')] for i in range(6))\n",
    "\n",
    "        def get_candidate(words, pos_cnt) -> str:\n",
    "            return max(words, key = score)\n",
    "\n",
    "        def full_match(word1, word2) -> int:\n",
    "            return sum(c1 == c2 for c1, c2 in zip(word1, word2))\n",
    "\n",
    "        def filter_words(can, words, match) -> List[str]:\n",
    "            res = []\n",
    "            for word in words:\n",
    "                if full_match(word, can) == match: # potential secret\n",
    "                    res.append(word)\n",
    "            return res\n",
    "\n",
    "        while words:\n",
    "            can = get_candidate(words, pos_cnt)\n",
    "            match = master.guess(can)\n",
    "            if match == 6:\n",
    "                return\n",
    "\n",
    "            words = filter_words(can, words, match)\n",
    "\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def findSecretWord(self, wordlist, master):\n",
    "        N = len(wordlist)\n",
    "        self.H = [[sum(a==b for a,b in zip(wordlist[i], wordlist[j]))\n",
    "                   for j in range(N)] for i in range(N)]\n",
    "\n",
    "        possible, path = range(N), ()\n",
    "        while possible:\n",
    "            guess = self.solve(possible, path)\n",
    "            matches = master.guess(wordlist[guess])\n",
    "            if matches == len(wordlist[0]): return\n",
    "            possible = [j for j in possible if self.H[guess][j] == matches]\n",
    "            path = path + (guess,)\n",
    "\n",
    "    def solve(self, possible, path = ()):\n",
    "        if len(possible) <= 2: return possible[0]\n",
    "\n",
    "        ansgrp, ansguess = possible, None\n",
    "        for guess, row in enumerate(self.H):\n",
    "            if guess not in path:\n",
    "                groups = [[] for _ in range(7)]\n",
    "                for j in possible:\n",
    "                    if j != guess:\n",
    "                        groups[row[j]].append(j)\n",
    "                maxgroup = max(groups, key = len)\n",
    "                if len(maxgroup) < len(ansgrp):\n",
    "                    ansgrp, ansguess = maxgroup, guess\n",
    "\n",
    "        return ansguess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def d(self, w1, w2):\n",
    "        d = 0\n",
    "        for i in range(6):\n",
    "            if w1[i] == w2[i]:\n",
    "                d += 1\n",
    "        return d\n",
    "\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        if len(words) == 1:\n",
    "            master.guess(words[0])\n",
    "            return\n",
    "        import random\n",
    "        # print(len(words))\n",
    "        i = random.randrange(0, len(words))\n",
    "        # print(\"guess: \", words[i])\n",
    "        res0 = master.guess(words[i])\n",
    "        if res0 == 6:\n",
    "            return\n",
    "        # print(\"input size: \", len(words), res0)\n",
    "        wl = []\n",
    "        for w in words:\n",
    "            # if w == words[i]:\n",
    "            #     continue\n",
    "            if self.d(w, words[i]) == res0:\n",
    "                wl.append(w)\n",
    "        self.findSecretWord(wl, master)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        def get(words):\n",
    "            n = len(words)\n",
    "            cnts = [[0 for _ in range(n)] for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    cnt = 0\n",
    "                    for k in range(6):\n",
    "                        if words[i][k] == words[j][k]: cnt += 1\n",
    "                    cnts[i][j] = cnt\n",
    "                    cnts[j][i] = cnt\n",
    "            mi = idx = -1\n",
    "            for i in range(n):\n",
    "                tmp = collections.Counter([cnts[i][j] for j in range(n) if i != j])\n",
    "                mx = max([tmp[k] for k in tmp])\n",
    "                if mi == -1 or mi > mx:\n",
    "                    mi, idx = mx, i\n",
    "            return idx, cnts[idx]\n",
    "        while len(words) >= 1:\n",
    "            if len(words) == 1:\n",
    "                master.guess(words[0])\n",
    "                return\n",
    "            idx, vals = get(words)\n",
    "            val, nexts = master.guess(words[idx]), []\n",
    "            if val == 'You guessed the secret word correctly.': return\n",
    "            for i, word in enumerate(words):\n",
    "                if i != idx and vals[i] == val: nexts.append(word)\n",
    "            words = nexts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        def diff(a,b):\n",
    "            res=0\n",
    "            for i in range(len(a)):\n",
    "                if a[i]==b[i]:\n",
    "                    res+=1\n",
    "            return res\n",
    "        \n",
    "        def var(l):\n",
    "            res=0\n",
    "            m=sum(l)/len(l)\n",
    "            return sum([(x-m)**2 for x in l])/len(l)\n",
    "\n",
    "        def minlen(words):\n",
    "            ti, tv = 0, inf\n",
    "            for i in range(len(words)):\n",
    "                s = [0]*7\n",
    "                for j in range(len(words)):\n",
    "                    s[diff(words[i], words[j])]+=1\n",
    "                v=var(s)\n",
    "                print(words[i], s, v)\n",
    "                if v<tv:\n",
    "                    tv, ti = v, i\n",
    "            return ti\n",
    "\n",
    "        res=words\n",
    "        while len(res)>1:\n",
    "            i=minlen(res)\n",
    "            print(i, res[i])\n",
    "            t=master.guess(res[i])\n",
    "            if t==6: break\n",
    "            s=[]\n",
    "            for _ in res:\n",
    "                if diff(res[i], _)==t:\n",
    "                    s.append(_)\n",
    "            print(res[i], t, s)\n",
    "            res=s\n",
    "        master.guess(res[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "import random\n",
    "random.seed(1234)\n",
    "\n",
    "\n",
    "def same(s1, s2):\n",
    "    cnt = 0\n",
    "    for i in range(len(s1)):\n",
    "        if s1[i] == s2[i]:\n",
    "            cnt += 1\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        n = len(words)\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                f[i][j] = same(words[i], words[j])\n",
    "                f[j][i] = f[i][j]\n",
    "        v2i = {v:i for i, v in enumerate(words)}\n",
    "        ans = None\n",
    "        candicates = words\n",
    "        vis = set()\n",
    "        while True:\n",
    "            i = random.randint(0, len(candicates)-1)\n",
    "            candicate = candicates[i]\n",
    "            v = master.guess(candicate)\n",
    "            if v == 6:\n",
    "                ans = candicate\n",
    "                break\n",
    "            else:\n",
    "                vis.add(i)\n",
    "                i = v2i[candicate]\n",
    "                new_candicates = []\n",
    "                for j in range(n):\n",
    "                    if f[i][j] == v and words[j] in candicates:\n",
    "                        new_candicates.append(words[j])\n",
    "                candicates = new_candicates\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        m = defaultdict(list)\n",
    "        for word1 in words:\n",
    "            for word2 in words:\n",
    "                diff = 0\n",
    "                for i in range(len(word1)):\n",
    "                    if word1[i] != word2[i]:\n",
    "                        diff += 1\n",
    "                m[word1, diff].append(word2)\n",
    "                \n",
    "        s = set(words)\n",
    "        while len(s) > 0:\n",
    "            same = master.guess(list(s)[0])\n",
    "            if same == 6: return \n",
    "            s &= set(m[list(s)[0], 6 - same])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is Master's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\r\n",
    "        n=len(words)\r\n",
    "        # samelarity=[{} for i in range(n)]\r\n",
    "        samelarity=[[0]*n for _ in range(n)]\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(i+1,n):\r\n",
    "                s=0\r\n",
    "                for k in range(6):\r\n",
    "                    if words[i][k]==words[j][k]:\r\n",
    "                        s+=1\r\n",
    "                samelarity[i][j]=s\r\n",
    "                samelarity[j][i]=s\r\n",
    "        flags=[False]*n\r\n",
    "        while True:\r\n",
    "            bound=n+1\r\n",
    "            canidate=0\r\n",
    "            for i in range(n):\r\n",
    "                if flags[i]:\r\n",
    "                    continue\r\n",
    "                dis=[0]*7\r\n",
    "                for s in samelarity[i]:\r\n",
    "                    dis[s]+=1\r\n",
    "                m=max(dis)\r\n",
    "                if m<bound:\r\n",
    "                    bound=m\r\n",
    "                    canidate=i\r\n",
    "\r\n",
    "            flags[canidate]=True\r\n",
    "            g=master.guess(words[canidate])\r\n",
    "            if g==6:\r\n",
    "                return\r\n",
    "            for j,s in enumerate(samelarity[canidate]):\r\n",
    "                if s!=g:\r\n",
    "                    flags[j]=True\r\n",
    "        \r\n",
    "# class Solution:\r\n",
    "#     def findSecretWord(self, wordlist, master):\r\n",
    "#         def distance(x,y):\r\n",
    "#             ans = 0\r\n",
    "#             for i in range(6):\r\n",
    "#                 if x[i] == y[i]:\r\n",
    "#                     ans += 1\r\n",
    "#             return ans\r\n",
    "#         \"\"\"\r\n",
    "#         :type wordlist: List[Str]\r\n",
    "#         :type master: Master\r\n",
    "#         :rtype: None\r\n",
    "#         \"\"\"\r\n",
    "#         dp = [0] * len(wordlist) #记录是否被排除\r\n",
    "#         for g in range(10):\r\n",
    "#             #寻找下一个猜测单词\r\n",
    "#             candidate = 0\r\n",
    "#             vote = float('inf')\r\n",
    "#             for i in range(len(wordlist)):\r\n",
    "#                 if dp[i] == 0:\r\n",
    "#                     dis = [0] * 7\r\n",
    "#                     for j in range(len(wordlist)):\r\n",
    "#                         if j != i and dp[j] == 0:\r\n",
    "#                             dis[distance(wordlist[i],wordlist[j])] += 1\r\n",
    "#                     if max(dis) < vote:\r\n",
    "#                         candidate = i\r\n",
    "#                         vote = max(dis)\r\n",
    "#             #猜测\r\n",
    "#             dp[candidate] = 1\r\n",
    "#             tmp = master.guess(wordlist[candidate])\r\n",
    "#             #排除不可能的单词\r\n",
    "#             for i in range(len(wordlist)):\r\n",
    "#                 if dp[i] == 0 and distance(wordlist[candidate],wordlist[i]) != tmp:\r\n",
    "#                     dp[i] = 1\r\n",
    "\r\n",
    "      \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "\n",
    "        while True:\n",
    "            m = len(words)\n",
    "            dis = [[0]*m for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(i+1, m):\n",
    "                    dis[i][j] = dis[j][i] = sum(words[i][k] == words[j][k] for k in range(6))\n",
    "            ind = list(range(m))\n",
    "            ind.sort(key=lambda it: -len(set(dis[it])))\n",
    "                    \n",
    "            word = words[ind[0]]\n",
    "            k = master.guess(word)\n",
    "            if k == 6:\n",
    "                return word\n",
    "            words = [w for w in words if sum(w[j] == word[j] for j in range(6)) == k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution(object):\n",
    "    def findSecretWord(self, wordlist, master):\n",
    "        N = len(wordlist)\n",
    "        # self.H = [[sum(a==b for a,b in itertools.izip(wordlist[i], wordlist[j]))\n",
    "        #            for j in range(N)] for i in range(N)]\n",
    "        self.H = [[0 for j in range(N)] for i in range(N)]\n",
    "        \n",
    "        for i in range(N):\n",
    "            for j in range(i+1, N):\n",
    "                count = 0\n",
    "                for k in range(6):\n",
    "                    count += wordlist[i][k] == wordlist[j][k]\n",
    "                self.H[i][j] = count\n",
    "                self.H[j][i] = count\n",
    "            \n",
    "            self.H[i][i] = 6\n",
    "        \n",
    "        print(self.H)\n",
    "\n",
    "        possible, path = range(N), set()\n",
    "        while possible:\n",
    "            guess = self.solve(possible, path)\n",
    "            matches = master.guess(wordlist[guess])\n",
    "            if matches == len(wordlist[0]): \n",
    "                return\n",
    "\n",
    "            possible = [j for j in possible if self.H[guess][j] == matches]\n",
    "            path.add(guess)\n",
    "\n",
    "    def solve(self, possible, path):\n",
    "        if len(possible) <= 2: \n",
    "            return possible[0]\n",
    "\n",
    "        ansgrp, ansguess = possible, None\n",
    "        for guess, row in enumerate(self.H):\n",
    "            if guess not in path:\n",
    "                groups = [[] for _ in range(7)]\n",
    "                for j in possible:\n",
    "                    if j != guess:\n",
    "                        groups[row[j]].append(j)\n",
    "                maxgroup = max(groups, key = len)\n",
    "                if len(maxgroup) < len(ansgrp):\n",
    "                    ansgrp, ansguess = maxgroup, guess\n",
    "\n",
    "        return ansguess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def cnt_same(w1, w2):\n",
    "        return sum(c1 == c2 for c1, c2 in zip(w1, w2))\n",
    "\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        maps = defaultdict(lambda: defaultdict(list))\n",
    "        for w1, w2 in combinations(words, 2):\n",
    "            cnt = self.cnt_same(w1, w2)\n",
    "            maps[w1][cnt].append(w2)\n",
    "            maps[w2][cnt].append(w1)\n",
    "        # print(maps)\n",
    "        \n",
    "        def get_score(m):\n",
    "            lst = [len(m[i]) for i in range(6)]\n",
    "            ave = sum(lst) / len(lst)\n",
    "            return sum([abs(i - ave) for i in lst])\n",
    "\n",
    "        scores = {w: get_score(maps[w]) for w in maps}\n",
    "        possible = [(w, s) for w, s in scores.items()]\n",
    "        time = 0\n",
    "        while len(possible) > 0:\n",
    "            g, score = min(possible, key=lambda x: x[1])\n",
    "            res = master.guess(g)\n",
    "            time += 1\n",
    "            if res == 6:\n",
    "                return\n",
    "            np = maps[g][res]\n",
    "            possible = [(w, s) for w, s in possible if w in np]\n",
    "            # 可以迭代maps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        N = len(words)\n",
    "        self.H = []\n",
    "        for i in range(N):\n",
    "            self.H.append([])\n",
    "            for j in range(N):\n",
    "                count = 0\n",
    "                for a, b in zip(words[i], words[j]):\n",
    "                    if a == b:\n",
    "                        count += 1\n",
    "                self.H[i].append(count)\n",
    "        possible, path = range(N), ()\n",
    "        while possible:\n",
    "            guess = self.solve(possible, path)\n",
    "            matches = master.guess(words[guess])\n",
    "            if matches == len(words[0]):\n",
    "                return \n",
    "            possible = [j for j in possible if self.H[guess][j] == matches]\n",
    "            path = path + (guess,)\n",
    "        \n",
    "    def solve(self, possible, path = ()):\n",
    "        ansgrp, ansguess = possible, None\n",
    "        for guess, row in enumerate(self.H):\n",
    "            if guess not in path:\n",
    "                groups = [[] for _ in range(7)]\n",
    "                for j in possible:\n",
    "                    if j != guess:\n",
    "                        groups[row[j]].append(j)\n",
    "                maxgroup = max(groups, key = len)\n",
    "                if len(maxgroup) < len(ansgrp):\n",
    "                    ansgrp, ansguess = maxgroup, guess\n",
    "        return ansguess                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def findSecretWord(self, wordlist, master):\n",
    "        \n",
    "        N = len(wordlist)\n",
    "        self.H = [[sum(a==b for a,b in zip(wordlist[i], wordlist[j]))\n",
    "                   for j in range(N)] for i in range(N)]\n",
    "\n",
    "        possible, path = range(N), ()\n",
    "        while possible:\n",
    "            guess = self.solve(possible, path)\n",
    "            matches = master.guess(wordlist[guess])\n",
    "            if matches == len(wordlist[0]): return\n",
    "            possible = [j for j in possible if self.H[guess][j] == matches]\n",
    "            path = path + (guess,)\n",
    "\n",
    "    def solve(self, possible, path = ()):\n",
    "        if len(possible) <= 2: return possible[0]\n",
    "\n",
    "        ansgrp, ansguess = possible, None\n",
    "        for guess, row in enumerate(self.H):\n",
    "            if guess not in path:\n",
    "                groups = [[] for _ in range(7)]\n",
    "                for j in possible:\n",
    "                    if j != guess:\n",
    "                        groups[row[j]].append(j)\n",
    "                maxgroup = max(groups, key = len)\n",
    "                if len(maxgroup) < len(ansgrp):\n",
    "                    ansgrp, ansguess = maxgroup, guess\n",
    "\n",
    "        return ansguess\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# consider a valid word list of n words, we can choose any wi out of it\n",
    "# assume with n words, there are xi words differs to wi by i letters\n",
    "# 0 <= i <= 6, x0 + x1 + ... + x6 = n\n",
    "# assuming that the answer is equally possible to be any of those words, i.e. 1/n chance for any word being correct\n",
    "# therefore if we guess wi, the response from master will be x0/n chance being 0, x1/n chance being 1, ...\n",
    "# if the response is j, only xj words will left to be valid, thus we are expecting\n",
    "# x0/n * x0 + x1/n * x1 + .. + x6/n * x6 = sum(xj^2, 0 <= j <= 6)/n words left\n",
    "# most efficient way would be to minimizes number of words left after each round\n",
    "# minimize sum(xj^2, 0 <= j <= 6)/n, subject to sum(xj, 0 <= j <= 6) = n, resulting x0 = x1 = .. = x6\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        n = len(words)\n",
    "        valid = set(range(n))\n",
    "        dists = [[6] * n for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                dists[i][j] = dists[j][i] = sum(1 if a == b else 0 for a, b in zip(words[i], words[j]))\n",
    "        \n",
    "        match = -1\n",
    "        while match < 6:\n",
    "            finder: dict[int, dict[int, int]] = {i: dict() for i in valid}\n",
    "            for i in valid:\n",
    "                for j in valid:\n",
    "                    if dists[i][j] not in finder[i]:\n",
    "                        finder[i][dists[i][j]] = 0\n",
    "                    finder[i][dists[i][j]] += 1\n",
    "\n",
    "            i = min(valid, key=lambda x: sum(v ** 2 for v in finder[x].values()))\n",
    "            match = master.guess(words[i])\n",
    "            for j in list(valid):\n",
    "                if dists[i][j] != match:\n",
    "                    valid.remove(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is Master's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "# class Master:\r\n",
    "#     def guess(self, word: str) -> int:\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\r\n",
    "        def distince(w1, w2):\r\n",
    "            return sum([s1 == s2 for s1, s2 in zip(w1, w2)])\r\n",
    "\r\n",
    "        l = len(words)\r\n",
    "        dist = {}\r\n",
    "        for i in range(l):\r\n",
    "            dis = {}\r\n",
    "            for j in range(l):\r\n",
    "                d = distince(words[i], words[j])\r\n",
    "                if d in dis.keys():\r\n",
    "                    dis[d].append(words[j])\r\n",
    "                else:\r\n",
    "                    dis[d] = [words[j]]\r\n",
    "            dist[words[i]] = dis\r\n",
    "\r\n",
    "        while True:\r\n",
    "            w = words[0]\r\n",
    "            d = master.guess(w)\r\n",
    "            if d == 6:\r\n",
    "                return w\r\n",
    "            else:\r\n",
    "                words = list(set(words)&set(dist[w][d]))\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        # 所谓极小化极大值实际上是让数据分布尽可能平均。选中一个数，可以从0～6画一个直方图，分别表示匹配0～6个字母的单词数。选中这个单词的话，如果猜错，那么剩下的就是其中直方图一条对应的单词。如果这个直方图不平均，那么就要看运气，剩下的可能多可能少。但尽可能让直方图平均，那么就可以比较稳定地缩小到原来1/6。所以每次要选最平均的单词。\n",
    "        # https://leetcode.cn/problems/guess-the-word/solutions/1632673/python3-by-qin-qi-shu-hua-2-o0vt/?company_slug=google\n",
    "        def helper(wordlist, times): # 单词列表，猜的次数\n",
    "            if time == 0:\n",
    "                return False\n",
    "            \n",
    "            l = len(wordlist)\n",
    "            if l <= times:\n",
    "                while master.guess(wordlist.pop()) != 6:\n",
    "                    pass\n",
    "                return True\n",
    "            # dp[i][j]代表与wordlist[i]匹配j个元素的word列表\n",
    "            dp = [[[] for _ in range(6)] for __ in range(l)]\n",
    "            for i in range(l):\n",
    "                for j in range(i + 1, l):\n",
    "                    count = sum([wordlist[i][k] == wordlist[j][k] for k in range(6)]) # 匹配个数\n",
    "                    dp[i][count].append(j)\n",
    "                    dp[j][count].append(i)\n",
    "            \n",
    "            m = float(\"inf\") #最大最小之差\n",
    "            for i in range(l):\n",
    "                p = [len(x) for x in dp[i]]\n",
    "                c = max(p) - min(p)\n",
    "                if c < m:\n",
    "                    m = c\n",
    "                    idx = i # 最平均的单词索引\n",
    "            c = master.guess(wordlist[idx])\n",
    "            if c == 6: # 如果猜中了，直接返回\n",
    "                return True\n",
    "            return helper([wordlist[i] for i in dp[idx][c]], times - 1) # 否则进入下一次\n",
    "        \n",
    "        return helper(words, 10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        # 所谓极小化极大值实际上是让数据分布尽可能平均。选中一个数，可以从0～6画一个直方图，分别表示匹配0～6个字母的单词数。选中这个单词的话，如果猜错，那么剩下的就是其中直方图一条对应的单词。如果这个直方图不平均，那么就要看运气，剩下的可能多可能少。但尽可能让直方图平均，那么就可以比较稳定地缩小到原来1/6。所以每次要选最平均的单词。\n",
    "        # https://leetcode.cn/problems/guess-the-word/solutions/1632673/python3-by-qin-qi-shu-hua-2-o0vt/?company_slug=google\n",
    "        def helper(wordlist, times): # 单词列表，猜的次数\n",
    "            if time == 0:\n",
    "                return False\n",
    "            \n",
    "            l = len(wordlist)\n",
    "            if l <= times:\n",
    "                while master.guess(wordlist.pop()) != 6:\n",
    "                    pass\n",
    "                return True\n",
    "            # dp[i][j]代表与wordlist[i]匹配j个元素的word列表\n",
    "            dp = [[[] for _ in range(6)] for __ in range(l)]\n",
    "            for i in range(l):\n",
    "                for j in range(i + 1, l):\n",
    "                    count = sum([wordlist[i][k] == wordlist[j][k] for k in range(6)]) # 匹配个数\n",
    "                    dp[i][count].append(j)\n",
    "                    dp[j][count].append(i)\n",
    "            \n",
    "            m = float(\"inf\") #最大最小之差\n",
    "            for i in range(l):\n",
    "                p = [len(x) for x in dp[i]]\n",
    "                c = max(p) - min(p)\n",
    "                if c < m:\n",
    "                    m = c\n",
    "                    idx = i # 最平均的单词索引\n",
    "            c = master.guess(wordlist[idx])\n",
    "            if c == 6: # 如果猜中了，直接返回\n",
    "                return True\n",
    "            return helper([wordlist[i] for i in dp[idx][c]], times - 1) # 否则进入下一次\n",
    "        \n",
    "        return helper(words, 10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is Master's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "# class Master:\n",
    "#     def guess(self, word: str) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def findSecretWord(self, words: List[str], master: 'Master') -> None:\n",
    "        # 所谓极小化极大值实际上是让数据分布尽可能平均。选中一个数，可以从0～6画一个直方图，分别表示匹配0～6个字母的单词数。选中这个单词的话，如果猜错，那么剩下的就是其中直方图一条对应的单词。如果这个直方图不平均，那么就要看运气，剩下的可能多可能少。但尽可能让直方图平均，那么就可以比较稳定地缩小到原来1/6。所以每次要选最平均的单词。\n",
    "        # https://leetcode.cn/problems/guess-the-word/solutions/1632673/python3-by-qin-qi-shu-hua-2-o0vt/?company_slug=google\n",
    "        def helper(wordlist, times): # 单词列表，猜的次数\n",
    "            if time == 0:\n",
    "                return False\n",
    "            \n",
    "            l = len(wordlist)\n",
    "            if l <= times:\n",
    "                while master.guess(wordlist.pop()) != 6:\n",
    "                    pass\n",
    "                return True\n",
    "            # dp[i][j]代表与wordlist[i]匹配j个元素的word列表\n",
    "            dp = [[[] for _ in range(6)] for __ in range(l)]\n",
    "            for i in range(l):\n",
    "                for j in range(i + 1, l):\n",
    "                    count = sum([wordlist[i][k] == wordlist[j][k] for k in range(6)]) # 匹配个数\n",
    "                    dp[i][count].append(j)\n",
    "                    dp[j][count].append(i)\n",
    "            \n",
    "            m = float(\"inf\") #最大最小之差\n",
    "            for i in range(l):\n",
    "                p = [len(x) for x in dp[i]]\n",
    "                c = max(p) - min(p)\n",
    "                if c < m:\n",
    "                    m = c\n",
    "                    idx = i # 最平均的单词索引\n",
    "            c = master.guess(wordlist[idx])\n",
    "            if c == 6: # 如果猜中了，直接返回\n",
    "                return True\n",
    "            return helper([wordlist[i] for i in dp[idx][c]], times - 1) # 否则进入下一次\n",
    "        \n",
    "        return helper(words, 10)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
